package com.sise.DP;

/**
 *      5. 最长回文子串
 *      输入：s = "babad"
 *      输出："bab"
 *      解释："aba" 同样是符合题意的答案。
 *
 *      题解：动态规划
 *      1、dp[][] 为状态，这里的数组用来存储 true，false，供右上角使用，也就是状态转移方程
 */
public class _05_longestPalindrome {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;

        int maxLen = 1;     // 最大长度
        int begin = 0;      // 起始点，终点为 起始点 + 最大长度

        // 1. 状态定义：dp[i][j] 表示 s[i...j]] 是否是回文串 true false
        // 2. 初始化
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();

        // 3. 状态转移
        // 注意：先填左下角，故此从 j 作为最外层循环
        // 填表规则：先一列一列的填写，再一行一行的填，保证左下方的单元格先进行计算
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {

                // 头尾字符不相等，不是回文串
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    // 相等的情况下，考虑头尾去掉后没有字串存在，或者剩下一个字符的时候，肯定就是回文串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];        // 状态转移，将左下角的 true 赋值给 当前位置
                    }
                }

                // 只要 dp[i][j] == true 成立（这是由上一步赋值得到的结果），就表示字串 s[i..j] 是回文，此时记录回文长度和起始位置
                // 一开始的想法是最后才进行查询，然而应该是每次得到 回文串后都进行比较长度，随时更新
                if (dp[i][j] == true && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}
